본문 바로가기
HOME> 저널/프로시딩 > 저널/프로시딩 검색상세

저널/프로시딩 상세정보

권호별목차 / 소장처보기

H : 소장처정보

T : 목차정보

Information and computation 19건

  1. [해외논문]   Editorial Board  


    Information and computation v.261 pt.2 ,pp. ii - ii , 2018 , 0890-5401 ,

    초록

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  2. [해외논문]   Special issue for the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan  

    Halldó , rsson, Magnú , s M.
    Information and computation v.261 pt.2 ,pp. 159 - 159 , 2018 , 0890-5401 ,

    초록

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  3. [해외논문]   Comparator Circuits over Finite Bounded Posets  

    Komarath, Balagopal (Corresponding author.) , Sarma, Jayalal , Sunil, K.S.
    Information and computation v.261 pt.2 ,pp. 160 - 174 , 2018 , 0890-5401 ,

    초록

    Abstract The comparator circuit model was originally introduced by Mayr et al. (1992) (and further studied by Cook et al. (2014)) to capture problems that are not known to be P -complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem and we know that NLOG ⊆ CC ⊆ P . Cook et al. (2014) showed that CC is also the class of languages decided by polynomial size comparator circuit families. We study generalizations of the comparator circuit model that work over fixed finite bounded posets. We observe that there are universal comparator circuits even over arbitrary fixed finite bounded posets. Building on this, we show the following: Comparator circuits of polynomial size over fixed finite distributive lattices characterize the class CC . When the circuit is restricted to be skew, they characterize LOG . Noting that (uniform) polynomial sized Boolean circuits (resp. skew) characterize P (resp. NLOG ), this indicates a comparison between P vs CC and NLOG vs LOG problems. Complementing this, we show that comparator circuits of polynomial size over arbitrary fixed finite lattices characterize the class P even when the comparator circuit is skew. In addition, we show a characterization of the class NP by a family of polynomial sized comparator circuits over fixed finite bounded posets . As an aside, we consider generalizations of Boolean formulae over arbitrary lattices. We show that Spira's theorem (Spira, 1971) can be extended to this setting as well and show that polynomial sized Boolean formulae over finite fixed lattices capture the class NC 1 . These results generalize results in Cook et al. (2014) regarding the power of comparator circuits. Our techniques involve design of comparator circuits and finite posets. We then use known results from lattice theory to show that the posets that we obtain can be embedded into appropriate lattices. Our results give new methods to establish CC upper bounds for problems and also indicate potential new approaches towards the problems P vs CC and NLOG vs LOG using lattice theoretic methods.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  4. [해외논문]   Proofs of proximity for context-free languages and read-once branching programs  

    Goldreich, Oded (Weizmann Institute, Israel ) , Gur, Tom (UC Berkeley, CA, USA ) , Rothblum, Ron D. (MIT and Northeastern University, MA, USA)
    Information and computation v.261 pt.2 ,pp. 175 - 201 , 2018 , 0890-5401 ,

    초록

    Abstract Proofs of proximity are proof systems wherein the verifier queries a sublinear number of bits, and soundness only asserts that inputs that are far from valid will be rejected. In their minimal form, called MA proofs of proximity ( MAP ) , the verifier receives, in addition to query access to the input, also free access to a short (sublinear) proof. A more general notion is that of interactive proofs of proximity ( IPP ) , wherein the verifier is allowed to interact with an omniscient, yet untrusted prover. We construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are: MAP s for these two classes, in which, for inputs of length n , both the verifier's query complexity and the length of the MAP proof are O ˜ ( n ) . IPP s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  5. [해외논문]   Linear-time list recovery of high-rate expander codes  

    Hemenway, Brett (University of Pennsylvania, Department of Computer and Information Science, United States ) , Wootters, Mary (Stanford University, Department of Computer Science, United States)
    Information and computation v.261 pt.2 ,pp. 202 - 218 , 2018 , 0890-5401 ,

    초록

    Abstract We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have applications to constructing efficiently list-decodable codes, as well as in compressed sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate 1 − ε for any ε > 0 . We can plug our high-rate codes into a construction of Alon and Luby (1996), recently highlighted by Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates R , which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. A slight strengthening of our result would imply linear-time and optimally list-decodable codes for all rates. Thus, our result is a step in the direction of solving this important problem.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  6. [해외논문]   Dynamic algorithms via the primal-dual method  

    Bhattacharya, Sayan (University of Warwick, Coventry, UK ) , Henzinger, Monika (University of Vienna, Austria ) , Italiano, Giuseppe (University of Rome Tor Vergata, Italy)
    Information and computation v.261 pt.2 ,pp. 219 - 239 , 2018 , 0890-5401 ,

    초록

    Abstract We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2 ) -approximately optimal solution in O ( f ⋅ log ⁡ ( m + n ) ) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b -matching problem, we maintain an O ( 1 ) -approximately optimal solution in O ( log 3 ⁡ n ) amortized update time, where n is the number of nodes in the graph.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  7. [해외논문]   An improved combinatorial algorithm for Boolean matrix multiplication  

    Yu, Huacheng
    Information and computation v.261 pt.2 ,pp. 240 - 247 , 2018 , 0890-5401 ,

    초록

    Abstract We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in O ˆ ( n 3 / log 4 ⁡ n ) time, where the O ˆ notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in O ˆ ( n 3 / log 3 ⁡ n ) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the “easy parts” of a given instance efficiently, we can solve the whole problem faster than n 3 .

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  8. [해외논문]   2-vertex connectivity in directed graphs  

    Georgiadis, Loukas (Department of Computer Science & Engineering, University of Ioannina, Greece ) , Italiano, Giuseppe F. (Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università) , Laura, Luigi (di Roma “Tor Vergata”, Italy ) , Parotsidis, Nikos (Dipartimento di Ingegneria Informatica, Automatica e Gestionale, “Sapienza” Università)
    Information and computation v.261 pt.2 ,pp. 248 - 264 , 2018 , 0890-5401 ,

    초록

    Abstract Given a directed graph, two vertices v and w are 2- vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v . In this paper, we show how to compute this relation in O ( m + n ) time, where n is the number of vertices and m is the number of edges of the graph. As a side result, we show how to build in linear time an O ( n ) -space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices v and w are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from v to w or in all paths from w to v .

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  9. [해외논문]   Block interpolation: A framework for tight exponential-time counting complexity  

    Curticapean, Radu
    Information and computation v.261 pt.2 ,pp. 265 - 280 , 2018 , 0890-5401 ,

    초록

    Abstract We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis # ETH introduced by Dell et al. (2014) . Our framework allows us to convert classical # P -hardness results for counting problems into tight lower bounds under # ETH , thus ruling out algorithms with running time 2 o ( n ) on graphs with n vertices and O ( n ) edges. As exemplary applications of this framework, we obtain tight lower bounds under # ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (2016) .

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  10. [해외논문]   Local reduction  

    Jahanjou, Hamidreza (Northeastern University, Boston, MA, United States ) , Miles, Eric (Google Inc., Los Angeles, CA, United States ) , Viola, Emanuele (Northeastern University, Boston, MA, United States)
    Information and computation v.261 pt.2 ,pp. 281 - 295 , 2018 , 0890-5401 ,

    초록

    Abstract We reduce non-deterministic time T ≥ 2 n to a 3SAT instance ϕ of quasilinear size | ϕ | = T ⋅ log O ( 1 ) ⁡ T such that there is an explicit NC 0 circuit C that encodes ϕ in the following way: on input a ( log ⁡ | ϕ | ) -bit index i , C outputs the i th clause of ϕ . The previous best result was C in NC 1 . Even in the simpler setting of polynomial size ( | ϕ | = poly ( T ) ), the previous best result was C in AC 0 . More generally, for any time T ≥ n and parameter r ≤ n we obtain | ϕ | = max ⁡ ( T , 2 n / r ) ⋅ ( n log ⁡ T ) O ( 1 ) , and each output bit of C is a decision tree of depth O ( log ⁡ r ) . As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지

논문관련 이미지